package leetcode.code0956;

import java.util.Arrays;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {
	int len;
	int[] rods;

	public int tallestBillboard(int[] rods) {
		len = rods.length;
		this.rods = rods;
		Integer[][] dp = new Integer[len][10000];
		int ans = f(0, 5000, dp);// 从第0个棍子开始开始，两根棍子高度差为0时，最长的棍子增加了多少。以5000为0点，将差值调整为正数以便dp
		return ans;
	}

	private int f(int idx, int diff, Integer[][] dp) {
		if (idx == len) {
			return diff == 5000 ? 0 : Integer.MIN_VALUE;// 所有棍子决策完毕，此时高度差是0：有效，没有棍子对长棍增加长度0，否则增加很小很小，后续决策中就会忽略这种选择
		}
		if (dp[idx][diff] != null) {
			return dp[idx][diff];
		}
		int ans = f(idx + 1, diff, dp);// 不要idx这个棍子，后续增加的长度与当前无关。
		int rod = rods[idx];// 当前棍子长度
		ans = Math.max(ans, rod + f(idx + 1, diff + rod, dp));// 长棍子增加了rod，高度差变为diff + rod
		ans = Math.max(ans, f(idx + 1, diff - rod, dp));// 加短棍子上了，高度差减少了
		dp[idx][diff] = ans;// 取max ，增加最长的返回
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(6, this.tallestBillboard(H.str2array3("[4,3,3,2]")));
		H.compare(6, this.tallestBillboard(H.str2array3("[3,4,3,3,2]")));
		H.compare(1757,
				this.tallestBillboard(H.str2array3("[235,227,284,275,246,238,256,249,238,236,231,264,239,261,271]")));
		H.compare(1023, this
				.tallestBillboard(H.str2array3("[1,2,4,8,16,32,64,128,256,512,50,50,50,150,150,150,100,100,100,123]")));
		H.compare(6, this.tallestBillboard(H.str2array3("[1,2,3,6]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution7 so = new Solution7();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
//		long ans = 0;
//		for (int i = 1; i < 20; i++) {
//			ans += Math.pow(2, i) * Math.pow(2, 20 - i);
//		}
//		System.out.println(ans);
	}

}
